import java.util.Arrays;

/**
 * @author hewei
 * @version 1.0
 * @description: 1140. 石子游戏 II
 * @date 2022/11/5 14:09
 */

public class StoneGameII {

    public static void main(String[] args) {
        int[] nums = {2,7,9,4,4};
        System.out.println(new StoneGameII().stoneGameII(nums));
    }

    int[][] dp1;
    int[][] dp2;
    public int stoneGameII1(int[] piles) {
        int n = piles.length;
        dp1 = new int[n][n];
        dp2 = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp1[i], -1);
            Arrays.fill(dp2[i], -1);
        }
        return f(piles, 0, 1);
    }

    public int f(int[] piles, int i, int m) {
        if (i >= piles.length) return 0;
        if (dp1[i][m] != -1) return dp1[i][m];
        int res = 0;
        int sum = 0;
        for (int j = 0; j < Math.min(2 * m, piles.length - i); j++) {
            sum += piles[j + i];
            res = Math.max(res, sum + s(piles, j + i + 1, Math.max(m, j + 1)));
        }
        dp1[i][m] = res;
        return res;
    }

    public int s(int[] piles, int i, int m) {
        if (i >= piles.length) return 0;
        if (dp2[i][m] != -1) return dp2[i][m];
        int res = Integer.MAX_VALUE;
        for (int j = 1; j <= Math.min(2 * m, piles.length - i); j++) {
            res = Math.min(res, f(piles, i + j, Math.max(m, j)));
        }
        dp2[i][m] = res;
        return res;
    }

    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n + 1];
        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            sum += piles[i];
            for (int j = 1; j < n + 1; j++) {
                if (i + 2 * j >= n) {
                    dp[i][j] = sum;
                } else {
                    for (int k = 1; k <= 2 * j; k++) {
                        // 我很聪明，所以会让对手在剩余的所有数中取得总和最小
                        dp[i][j] = Math.max(dp[i][j], sum - dp[i + k][Math.max(k, j)]);
                    }
                }
            }
        }
        return dp[0][1];
    }
}
